package com.zhugang.week04;

/**
 * @program algorithms
 * @description: reversePairs
 * @author: chanzhugang
 * @create: 2022/07/01 09:26
 */
public class ReversePairs2 {

    public static void main(String[] args) {
        ReversePairs2 reversePairs2 = new ReversePairs2();
        int[] nums = new int[]{7, 5, 6, 4};
        int count = reversePairs2.reversePairs(nums);
        System.out.println(count);
    }

    /**
     * 剑指offer 51 数组中的逆序对
     *
     * @param nums
     * @return
     */

    int reverseCount = 0;

    public int reversePairs(int[] nums) {
        // 逆序对个数 = 逆序度 排序就是减少逆序度的过程, 利用归并排序
        mergeSort(nums, 0, nums.length - 1);
        return reverseCount;
    }

    private void mergeSort(int[] nums, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = (p + r) / 2;
        mergeSort(nums, p, q);
        mergeSort(nums, q + 1, r);
        merge(nums, p, q, r);
    }

    private int merge(int[] nums, int p, int q, int r) {
        // 合并两个有序数组： 双指针i、j
        int i = p;
        int j = q + 1;
        int[] tmp = new int[r - p + 1];
        int k = 0;
        while (i <= q && j <= r) {
            if (nums[j] < nums[i]) {
                // 逆序度：值小下标大
                reverseCount += (q - i + 1);
                tmp[k++] = nums[j++];
            } else {
                tmp[k++] = nums[i++];
            }
        }
        while (j <= r) {
            tmp[k++] = nums[j++];
        }
        while (i <= q) {
            tmp[k++] = nums[i++];
        }
        for (int l = 0; l < r - p + 1; l++) {
            nums[p + l] = tmp[l];
        }
        return reverseCount;

    }

}